import java.util.*;

public class demo1 {
    public int[] findOrder(int n, int[][] p) {
        //记录该点的入度
        int[] in = new int[n];
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < p.length; i++) {
            int x = p[i][0];
            int y = p[i][1];//y->x
            if (!map.containsKey(y)) {
                map.put(y, new ArrayList<>());
            }
            map.get(y).add(x);
            in[x]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) queue.add(i);
        }
        int[] dp = new int[n];
        int index = 0;
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            dp[index++] = poll;
            List<Integer> list = map.getOrDefault(poll, new ArrayList<>());
            for (Integer temp : list) {
                in[temp]--;
                if (in[temp] == 0) {
                    queue.add(temp);
                }
            }
        }
        if (index == n) return dp;
        return new int[0];
    }

    public int[] findOrder1(int n, int[][] p) {
        //记录该点的入度
        int[] in = new int[n];
        List<List<Integer>> list = new ArrayList<>();
        //计入的是n个
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < p.length; i++) {
            int x = p[i][0];
            int y = p[i][1];//y->x
            list.get(y).add(x);
            in[x]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) queue.add(i);
        }
        int[] dp = new int[n];
        int index = 0;
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            dp[index++] = poll;
            List<Integer> integers = list.get(poll);
            for (Integer temp : integers) {
                in[temp]--;
                if (in[temp] == 0) {
                    queue.add(temp);
                }
            }
        }
        if (index == n) return dp;
        return new int[0];
    }
}
